package aws;

import java.util.HashMap;
import java.util.Map;

public class SubArrayIndex {

    /**
     * 计算前缀和，并记录每个位置前缀和的值
     * 用前缀和的值减去k,如果差值在map中存在，则找到
     * @param array
     * @param k
     * @return
     */
    public int subArrayIndex(int []array, int k) {

        int j = 0;
        int sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        do{
            sum = sum + array[j];
            if(sum == k) {
                return j + 1;
            }

            if(map.get(sum) == null) {
                map.put(sum, j);
            }

            Integer index = map.get(sum - k);
            if(index != null) {
                return j - index;
            }
            j++;
        } while (j < array.length);

        return -1;
    }

    public static void main(String[] args) {
        System.out.println(new SubArrayIndex().subArrayIndex(new int[]{1,0,0,0,2,0,3,4,5}, 5));
        System.out.println(new SubArrayIndex().subArrayIndex(new int[]{1,2,3,4,5}, 5));
        System.out.println(new SubArrayIndex().subArrayIndex(new int[]{3,5,7,10,2},12));
        System.out.println(new SubArrayIndex().subArrayIndex(new int[]{3,5,7,10,2},19));
    }
}
